package com.example.demo.java.container.map;

import java.util.LinkedHashMap;

/**
 * 有顺序的HashMap
 *
 * LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，
 * 解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，
 * LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，
 * 比如缓存。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法
 */
public class UDLinkedHashMap {

    /** 1.数据结构：继承自HashMap，数组+链表/红黑树+保证顺序的before/after(双向链表) */
        /** 如果是false，则用存储排序，true用访问排序，LinkedHashMap的构造方法默认都是false */
        // final boolean accessOrder;

    /** 2.核心源码分析 */
        /** 2.1 双向链表初始变量
                每当有新键值对节点插入，新节点最终会接在 tail 引用指向的节点后面。
                而 tail 引用则会移动到新的节点上，这样一个双向链表就建立起来了。 */
                  /** 双向链表的头 */
            //    transient LinkedHashMap.Entry<K, V> head;
                  /** 双向链表的尾 */
            //    transient LinkedHashMap.Entry<K, V> tail;

        /** 2.2 插入元素 */
                  /** LinkedHashMap 覆写了该方法。在这个方法中，LinkedHashMap 创建了 Entry，
                        并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部，实现了双向链表的建立。
                        双向链表建立之后，我们就可以按照插入顺序去遍历 LinkedHashMap */
            //    HashMap.Node<K, V> newNode(int hash, K key, V value, HashMap.Node<K, V> e) {
            //        LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry(hash, key, value, e);
                      /** 将 Entry 接在双向链表的尾部 */
            //        this.linkNodeLast(p);
            //        return p;
            //    }
                    /** 存储双向链表 */
            //      private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
            //          LinkedHashMap.Entry<K, V> last = this.tail;
                        /** 1.将新插入的节点赋值给尾节点 */
            //          this.tail = p;
                        /** 2.last 为 null，表明双向链表还未建立 */
            //          if (last == null) {
                            /** 3.设置双向链表的头为当前节点 */
            //              this.head = p;
            //          } else {
                            /** 4.当前节点的前驱引用设置为last，即原双向列表的最后节点 */
            //              p.before = last;
                            /** 5.将最后一个节点的后继引用设置为当前节点 */
            //              last.after = p;
            //          }
            //
            //      }

        /** 2.3 删除节点时调用 afterNodeRemoval */
                  // LinkedHashMap 中覆写
            //    void afterNodeRemoval(Node<K,V> e) { // unlink
                      /** 1.获取要删除的节点及其前驱、后继引用 */
            //        LinkedHashMap.Entry<K,V> p =
            //                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                      /** 2.先将删除节点的前驱、后继清空 */
            //        p.before = p.after = null;
                      /** 3.b 为 null，表明 p 是头节点 */
            //        if (b == null)
                          /** 4.设置双向链表的头为当前节点的后继引用 */
            //            head = a;
            //        else
                          /** 5.不是头节点，赋值前驱引用的后继引用为当前节点的后继引用 */
            //            b.after = a;
                      /** 6.a 为 null，表明 p 是尾节点 */
            //        if (a == null)
                          /** 7.将最后节点设置为当前节点的前驱引用 */
            //            tail = b;
            //        else
                          /** 8.不是尾节点，赋值后继引用的前驱引用为当前节点的前驱引用 */
            //            a.before = b;
            //    }

        /** 2.4 当排序顺序为访问顺序时，afterNodeAccess将操作对象放到尾部 */
            //    void afterNodeAccess(HashMap.Node<K, V> e) {
            //        LinkedHashMap.Entry last;
                      /** 1.当accessOrder为true且双向链表的尾部节点不等于当前操作的节点，将当前操作的节点移动至尾部 */
            //        if (this.accessOrder && (last = this.tail) != e) {
            //            LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry)e;
                          /** 2.b是当前节点的前驱引用 */
            //            LinkedHashMap.Entry<K, V> b = p.before;
                          /** 3.a是当前节点的后继引用 */
            //            LinkedHashMap.Entry<K, V> a = p.after;
                          /** 4.因为要将当前节点移动至尾部，所以后继引用置空 */
            //            p.after = null;
                          /** 5.如果b是空，代表当前节点为头节点 */
            //            if (b == null) {
                              /** 6.将头节点设置为a，即当前节点的后继引用 */
            //                this.head = a;
            //            } else {
                              /** 7.不是头部时，则将b的后继引用直接赋值为a */
            //                b.after = a;
            //            }
                          /** 8.如果a不是空，将a的前驱引用设置为b */
            //            if (a != null) {
            //                a.before = b;
            //            } else {
                              /** 9.本身就是最后一个节点，则设置last为b */
            //                last = b;
            //            }
                          /** 10.last为空，表明双向链表还未建立 */
            //            if (last == null) {
                              /** 11.直接将当前节点设置为头节点 */
            //                this.head = p;
            //            } else {
                              /** 12.当前节点的前驱引用设置为原来的最后一个节点 */
            //                p.before = last;
                              /** 13.将原来的最后一个节点的后继引用设置为当前节点 */
            //                last.after = p;
            //            }
                          /** 14.设置当前节点为双向链表的尾节点 */
            //            this.tail = p;
            //            ++this.modCount;
            //        }
            //
            //    }

        /** 2.5 基于 LinkedHashMap 实现缓存LUA策略缓存  afterNodeInsertion */
            //    void afterNodeInsertion(boolean evict) {
            //        LinkedHashMap.Entry first;
                      /** 符合条件，会删除指定数据，可用于实现LUA策略缓存（排序方式基于访问排序），如长时间未登陆过的用户，删除掉 */
            //        if (evict && (first = this.head) != null && this.removeEldestEntry(first)) {
            //            K key = first.key;
            //            this.removeNode(hash(key), key, (Object)null, false, true);
            //        }
            //
            //    }
                  /** 删除的条件，需要重写此方法，实现自己的业务逻辑 */
            //    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
            //        return false;
            //    }

    /** 3.基于LinkedHashMap实现LRU策略缓存(活跃数据放在最后) */

}
